//给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 
//
// 两个相邻元素间的距离为 1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
//输出：[[0,0,0],[0,1,0],[0,0,0]]
// 
//
// 示例 2： 
//
// 
//
// 
//输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
//输出：[[0,0,0],[0,1,0],[1,2,1]]
// 
//
// 
//
// 提示： 
//
// 
// m == mat.length 
// n == mat[i].length 
// 1 <= m, n <= 10⁴ 
// 1 <= m * n <= 10⁴ 
// mat[i][j] is either 0 or 1. 
// mat 中至少有一个 0 
// 
//
// Related Topics 广度优先搜索 数组 动态规划 矩阵 👍 757 👎 0

package leetcode.editor.cn;


import java.util.LinkedList;
import java.util.Queue;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution542 {
    /**
     * BFS,广度优先搜索中每个位置最多只会被加入队列一次，因此只需要 O(mn)O(mn) 的时间复杂度。
     */
    public int[][] updateMatrix(int[][] mat) {
        int[][] delta = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        int m = mat.length, n = mat[0].length;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    visited[i][j] = true;
                    queue.offer(new int[]{i, j});
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            for (int d = 0; d < 4; d++) {
                int i = poll[0] + delta[d][0], j = poll[1] + delta[d][1];
                if(i >=0 && i <m && j >=0 && j<n && !visited[i][j]){
                    mat[i][j] = mat[poll[0]][poll[1]] + 1;
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        return mat;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
